A graph is unipolar if it can be partitioned into a clique and a disjoint union of\ncliques, and a graph is a generalised split graph if it or its complement is unipolar. A unipolar\npartition of a graph can be used to find efficiently the clique number, the stability number, the\nchromatic number, and to solve other problems that are hard for general graphs. We present\nan O(n2)-time algorithm for recognition of n-vertex generalised split graphs, improving on\nprevious O(n3)-time algorithms.
Loading....